#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10
#define ARRAY_LENGTH(arr) (sizeof(arr) / sizeof(arr[0]))
void PrintList(int *list, int len);
// 冒泡排序
void BubbleSort(int list[MAX_SIZE]);
// 直接插入排序
void DrictInsertSort(int *list);
void DrictInsertSort2(int list[MAX_SIZE]);
// 折半插入排序
void BinaryInsertSort(int list[MAX_SIZE]);
// 希尔排序
void ShellSort(int list[MAX_SIZE]);
// 快速排序
void QucikSort(int *list,int low, int high);
int Partion(int *list, int low, int high);
// 简单选择排序
void SelectSort(int list[MAX_SIZE]);
// 堆排序
void HeapSort(int list[MAX_SIZE]);
// 归并排序
void MergeSort(int *list, int low, int high);
void Merge(int *list, int low,int mid, int high);


void main(){
    int list1[MAX_SIZE] = { 2, 3, 5, 1, 6, 10, 9, 4, 8, 7 };
    PrintList(list1, MAX_SIZE);
    
    BubbleSort(list1);

    // memcpy(list2, list1, 10)
    int list2[11] = { 65535, 2, 3, 5, 1, 33, 10, 9, 4, 8, 7 };
    PrintList(list2, MAX_SIZE);
    DrictInsertSort(list2);
    int list22[MAX_SIZE] = { 66, 2, 5, 1, 6, 10, 9, 4, 8, 7 };
    PrintList(list22, MAX_SIZE);
    DrictInsertSort2(list22);

    int list3[MAX_SIZE] = { 2, 3, 5, 1, 6, 10, 9, 4, 8, 7 };
    PrintList(list3, MAX_SIZE);
    BinaryInsertSort(list3);

    int list4[MAX_SIZE] = { 200, 3, 5, 1, 6, 11, 90, 4, 8, 7 };
    PrintList(list4, MAX_SIZE);
    ShellSort(list4);

    int list5[MAX_SIZE] = { 20, 3, 5, 1, 6, 10, 9, 4, 45, 7 };
    PrintList(list5, MAX_SIZE);
    QucikSort(list5, 0, 9);
    printf("QuickSort:");
    PrintList(list5, MAX_SIZE);

    int list6[MAX_SIZE] = { 2, 3, 50, 1, 6, 10, 9, 4, 8, 7 };
    PrintList(list6, MAX_SIZE);
    SelectSort(list6);

    int list7[MAX_SIZE] = { 2, 3, 5, 1, 6, 10, 9, 4, 8, 7 };
    HeapSort(list7);

    int list8[MAX_SIZE] = { 2, 3, 5, 1, 6, 10, 9, 4, 8, 7 };
    PrintList(list8, MAX_SIZE);
    MergeSort(list8, 0, 9);
    printf("MergeSort:");
    PrintList(list8, MAX_SIZE);
}

void PrintList(int *list, int len){
    for(int i = 0; i < len; i++){
        printf("%d ", list[i]);
    }
    printf("\n");
}

void BubbleSort(int list[MAX_SIZE]){
    for(int i = 0; i < MAX_SIZE; i++){
        for(int j = 0; j < MAX_SIZE - i - 1; j++){
            if(list[j] > list[j+1]){
                int tmp = list[j];
                list[j] = list[j+1];
                list[j+1] = tmp;
            }
        }
    }
    printf("BubbleSort:");
    PrintList(list, MAX_SIZE);
}


void DrictInsertSort(int *list){
    int j;
    for(int i=2; i < 11; i++){
        if(list[i]<list[i-1]){
            list[0] = list[i];
            for(j = i -1; list[j] > list[0] && j > 0 ;j--){
                list[j+1] = list[j];
            }
            list[j+1]=list[0];
        }
    }
    list[0] = 65536;
    printf("DrictInsertSort:");
    PrintList(list, 11);
}

void DrictInsertSort2(int list[MAX_SIZE]){
    int tmp, j;
    for(int i=1; i < MAX_SIZE; i++){
        if(list[i]<list[i-1]){
            tmp = list[i];
            for(j = i - 1; list[j] > tmp && j >= 0 ;j--){
                list[j+1] = list[j];
            }
            list[j+1]=tmp;
        }
    }
    printf("DrictInsertSort2:");
    PrintList(list, MAX_SIZE);
}

void BinaryInsertSort(int list[MAX_SIZE]){
    printf("BinaryInsertSort:\n");

}

void ShellSort(int list[MAX_SIZE]){
    int tmp, j;
    for(int d=MAX_SIZE/2; d > 0; d/=2){
        // 数组从0开始则不需要d+1
        for(int i = d; i < MAX_SIZE; i++){
            if(list[i]<list[i-d]){
                tmp = list[i];
                for(j = i - d; list[j] > tmp && j>=0; j-=d){
                    list[j+d]=list[j];
                }
                list[j+d]=tmp;
            }
        }
    }
    printf("ShellSort:");
    PrintList(list, MAX_SIZE);
}

void QucikSort(int *list, int low, int high){
    if(low<high){
        int p = Partion(list, low, high);
        QucikSort(list, low, p-1);
        QucikSort(list, p+1, high);
    }
    
}

int Partion(int *list, int low, int high){
    int tmp = list[low];
    while(low<high){
        while(low<high && list[high]>tmp)high--;
        list[low]=list[high];
        while(low<high && list[low]<tmp)low++;
        list[high]=list[low];
    }
    list[low] = tmp;
    return low;
}

void SelectSort(int list[MAX_SIZE]){
    int min;
    for(int i=0; i<MAX_SIZE;i++){
        min = i;
        for(int j = i+1; j < MAX_SIZE;j++){
            if(list[j]<list[min]){
                int tmp = list[min];
                list[min] = list[j];
                list[j] = tmp;
            }
        }
    }
    printf("SelectSort:");
    PrintList(list, MAX_SIZE);
}

void HeapSort(int list[MAX_SIZE]){
    printf("HeapSort:\n");
}

void MergeSort(int list[MAX_SIZE], int low, int high){
    if(low < high){
        int mid = (low+high)/2;
        MergeSort(list, low, mid);
        MergeSort(list, mid+1, high);
        Merge(list, low, mid, high);
    }
}

void Merge(int *list, int low,int mid, int high){
    int tmpArr[MAX_SIZE];
    for(int i = low; i <= high; i++){
        tmpArr[i] = list[i];
    }
    // 注意k的起始位置和for循环停止条件
    int j = low, k = mid+1, l=low;
    for(;j <= mid && k <= high; l++ ){
        if(tmpArr[j]<tmpArr[k]){
            list[l] = tmpArr[j++];
        }else{
            list[l] = tmpArr[k++];
        }
    }

    while(j<=mid){
        list[l++]=tmpArr[j++];
    }

    while(k<=high){
        list[l++]=tmpArr[k++];
    }
}